# 树可以看成是一个连通且 无环 的 无向 图。
# 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。
# 添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。
# 图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
#
# 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
#  示例 1：
# 输入: edges = [[1,2], [1,3], [2,3]]
# 输出: [2,3]
#
#  示例 2：
# 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
# 输出: [1,4]

from functools import reduce
from typing import List


class Solution:
    """
    解法二：并查集
    """

    def findRedundantConnection2(self, edges: List[List[int]]) -> List[int]:
        pass

    '''
    解法一：dfs
    每次向图中添加一条边，然后进行 dfs 遍历出边数组表示的图，查看是否有环，无环就进行下一次操作
    '''

    def findRedundantConnection1(self, edges: List[List[int]]) -> List[int]:
        n = reduce(lambda init_val, e: max(init_val, e[0], e[1]), edges, -1)
        for x, y in edges:
            n = max(n, x, y)
        graph = [[] for _ in range(n + 1)]
        visited, has_recycle = [False] * (n + 1), False

        def dfs(node: int, father: int) -> None:  # dfs 判断是否有环
            nonlocal has_recycle
            visited[node] = True
            for neighbor in graph[node]:
                if neighbor == father:
                    continue
                if not visited[neighbor]:
                    dfs(neighbor, node)
                else:
                    has_recycle = True
                    return

        # 遍历边
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
            # 每加入一条边便 dfs 搜索是否有环
            dfs(x, -1)
            if has_recycle:  # 如果本次添加边导致出现了环，就返回
                return [x, y]
            visited = [False] * (n + 1)
        return []

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        return self.findRedundantConnection1(edges)


if __name__ == "__main__":
    edges = [[1, 2], [1, 3], [2, 3]]
    edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
    res = Solution().findRedundantConnection(edges)
    print(res)
